# 数组的相对排序: https://leetcode-cn.com/problems/relative-sort-array/

# 自己想的笨办法， 依次再arr1中查找 arr2 中的元素 替换到开头，再对后面进行排序
class Solution:
    def relativeSortArray(self, arr1: list, arr2: list) -> list:
        """
            线性遍历,O(n^2)，再对后面的结果进行排序， 勉强能通过
        """
        # 1. 定义双指针 i, j  j往前一直找 arr2 中相同的值，往 i前面放
        i = 0
        for num in arr2:
            j = i
            while j < len(arr1):
                if arr1[j] == num:
                    arr1[i], arr1[j] = arr1[j], arr1[i]
                    i += 1
                j += 1
        
        # 2. 再对后面进行排序
        n1, n2 = len(arr1), len(arr2)
        tempList = sorted(arr1[i:n1])
        arr1[i:n1] = tempList
        return arr1



class Solution:
    def relativeSortArray(self, arr1: list, arr2: list) -> list:
        """
            升级一下也就是说，现在的这个是自定义的排序，按照新的比较规则进行排序即可
            比较规则：
            1. arr2中出现的靠前的元素 小于 靠后的元素
            2. 没有在arr2 中出现的元素， 按照正常比较
            3. arr2 中出现的元素比没出现的小

            在Python中可以使用元组进行（num, i） num表示元素值， i代表arr2中它出现的下标
            没有在arr2中出现的话，就规定为原本数值 + n2, n2为 arr2的长度
        """
        n1, n2 = len(arr1), len(arr2)
        # 1. 构造比较字典：
        sortMap = {arr2[i]: i for i in range(n2)}
        # 2. 构造比较函数
        def bySort(num):
            return sortMap.get(num, num + n2)

        # 3. 进行比较
        arr1.sort(key = bySort)

        return arr1


# 上面的方法使用匿名函数优化后，只需要写两行代码
class Solution:
    def relativeSortArray(self, arr1: list, arr2: list) -> list:
        # 1. 构造比较字典：
        sortMap = {arr2[i]: i for i in range(len(arr2))}
        # 2. 进行比较排序
        arr1.sort(key = lambda num: sortMap.get(num, num + len(arr2)))

        return arr1


# 计数排序
class Solution:
    def relativeSortArray(self, arr1: list, arr2: list) -> list:
        """
            观察整数的范围是在 0-1000内，不算大，可以使用计数排序解答
        """
        rMax = max(arr1)
        countList = [0] * (rMax + 1)
        n1 = len(arr1)
        # 1. 计数
        for i in range(n1):
            countList[arr1[i]] += 1
        ans = list()
        # 2. 使用 extend() 方法效率要高于 append(), 避免了频繁扩容 
        for num in arr2:
            ans.extend([num] * countList[num]) 
            # 不能忘记置0
            countList[num] = 0
        # 3. 将arr2 中不存在的元素也加进去
        for i in range(rMax + 1):
            if countList[i] > 0:
                ans.extend([i] * countList[i])

        return ans
            